package SwordFingerOffer;

public class Q68_1_LowestCommonAncestor {
    //二叉搜索树最低公共祖先

    class Info {
        TreeNode ans ;
        boolean pExist;
        boolean qExist;
        public Info(boolean pExist, boolean qExist, TreeNode ans) {
            this.pExist = pExist;
            this.qExist = qExist;
            this.ans = ans;
        }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        return process(root, p, q).ans;
    }

//    //通用
//    public Info process(TreeNode root, TreeNode p, TreeNode q){
//
//        if (root == null){
//            return new Info(false, false, null);
//        }
//        boolean pExist = false;
//        boolean qExist = false;
//        TreeNode ans = null;
//        Info leftInfo = process(root.left, p, q);
//        Info rightInfo = process(root.right, p, q);
//        if (leftInfo.qExist || rightInfo.qExist || root == q ){
//            qExist = true;
//        }
//        if (leftInfo.pExist || rightInfo.pExist || root == p ){
//            pExist = true;
//        }
//
//
//        if (leftInfo.ans != null || rightInfo.ans != null){
//            ans = leftInfo.ans != null ? leftInfo.ans : rightInfo.ans;
//        }
//        else if (pExist && qExist){
//            ans = root;
//        }
//
//        return new Info(pExist ,qExist ,ans);
//    }

    //通用 ==> 利用二叉搜索树剪枝
    public Info process(TreeNode root, TreeNode p, TreeNode q){

        if (root == null){
            return new Info(false, false, null);
        }
        boolean pExist = false;
        boolean qExist = false;
        TreeNode ans = null;

        Info leftInfo = process(root.left, p, q);
        Info rightInfo = process(root.right, p, q);
        if (leftInfo.qExist || rightInfo.qExist || root == q ){
            qExist = true;
        }
        if (leftInfo.pExist || rightInfo.pExist || root == p ){
            pExist = true;
        }
        if (leftInfo.ans != null || rightInfo.ans != null){
            ans = leftInfo.ans != null ? leftInfo.ans : rightInfo.ans;
        }
        else if (pExist && qExist){
            ans = root;
        }

        return new Info(pExist ,qExist ,ans);
    }


    public static void main(String[] args) {
        Q68_1_LowestCommonAncestor fun = new Q68_1_LowestCommonAncestor();
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        root.left.right.left = new TreeNode(3);
        root.left.right.right = new TreeNode(5);
        TreeNode node = fun.lowestCommonAncestor(root, new TreeNode(2), new TreeNode(8));
        System.out.println(node.val);

    }
}
